1. Field of the Invention
This invention relates generally to a method and apparatus for (1) receiving a measured signal produced directly or indirectly from a signal that is received from a measuring device (2) to efficiently determining a mean and a covariance of a nonlinear transformation of the measured signal and (3) transmitting a resulting signal representing the determined mean and covariance in order to evoke a response related to the measured signal. The response is a physical response from a system receiving the resulting signal. This invention also relates generally to the corresponding signal processing method.
This invention also relates to a signal processing system which is programmed or specialized for estimating the expected value and covariance of a nonlinear function of a measured signal, wherein the nonlinear function is a model of a system which assumes that the measured signal is a measure of at least one of the variables of the modeled system, and for evoking a physical response, and to the corresponding signal processing method.
2. Discussion of Background and Prior Art
The signal processing problem addressed by the current invention is to receive a mean and covariance estimate derived from measurements of a physical system and efficiently apply a nonlinear transformation to that estimate in order to determine the past or future values of variables relating to the physical system, or to nonlinearly transform quantities relating to the physical system to a different coordinate system.
A typical example of where such a signal processing problem arises is a tracking system that maintains an estimate of the position, speed, and bearing of a ballistic missile derived from periodic radar measurements of the position of the missile. Known physical laws governing ballistic motion yield a nonlinear transformation which can be applied to a state vector containing values relating to the position, speed, and bearing of the missile at a given time to estimate any past or future position of the missile between its launch and destination points. The ability to determine future positions of missiles is critical for missile defense systems which must deploy a weapon to impact a missile at a future point in its trajectory.
In the case of a missile tracking system it is often also the case that the state vector maintained by the tracking system is represented in a spherical coordinate system determined by the position of the radar. In order to deploy a remotely located weapon that does not have information about this coordinate system, however, it is necessary to nonlinearly transform the predicted position estimate of the missile to a globally known coordinate system. The application of nonlinear transformations to a state vector which has no associated uncertainty is generally straightforward, but if the state vector represents only an expected value which has an associated covariance matrix defining the uncertainty in the state estimate, then the application of a nonlinear transformation becomes extremely difficult.
A signal herein is defined as any measurable quantity that is related to the changing of the physical state of a process, system, or substance. A signal includes, but is not limited to, radiation produced by a natural or man-made process, electrical fluctuations produced by a natural or a man-made process, distinctive materials or chemicals produced by a natural or man-made process, distinctive structures or configurations of materials produced by a natural or a man-made process, or distinctive patterns of radiation or electrical activity produced by a natural or man-made process.
Most generally, a signal representing a measurement of any physical system inherently has some degree of random error associated therewith. Thus, the model of any physical system, if it is to accurately account for that random error, must include a way to estimate the expected values and uncertainties in the values of the physical system that occur due to the random error.
The measurement of a signal is provided by a measuring device. A measuring device as defined herein may be, but is not limited to, any physical device that interacts with a physical system and provides information that can be converted into an estimate comprised of a nominal estimate of the state of the system and an estimate of the error associated with that nominal state estimate. A measuring device as defined herein includes any device that emits a signal and measures the change of the signal upon its return, a device that measures a signal that is naturally produced by a physical process, or any device that measures a signal that is produced by a man-made process.
In one of the most common formulations of the signal processing problem, each estimate is represented as, or can be converted to, a pair comprising a state vector (often referred to as the mean) a and an error matrix A, denoted {a,A}. The state vector a is a (column) vector composed of m elements in which element a.sub.i corresponds to a variable, such as size or temperature, describing the state of a system of interest. The error matrix A is a matrix having m rows and m columns in which the element A.sub.ij, for any choice of i and j between 1 and m, is related to the expected value of the product of the errors associated with the values stored in elements a.sub.i and a.sub.j. If the value of element A.sub.ij is precisely the expected value of the product of the errors associated with the values stored in elements a.sub.i and a.sub.j, for any choice of i and j between 1 and m, then A is referred to as the error covariance of the estimated state vector a.
The error matrix A is often referred to as a covariance matrix according to a general definition of a covariance matrix as being a symmetric matrix with nonnegative eigenvalues, but A is not in general the true error covariance T associated with the state estimate a because T is usually unknown. The standard practice is to choose A large enough that it can be assumed to be of the form A=T+E, where E is an unknown covariance matrix representing the overestimated components of A. An overestimated covariance matrix is said to be "conservative" because it suggests that the state estimate is less accurate than it actually is. This is preferred to an underestimated covariance that suggests that the state estimate is more accurate than it actually is. For example, an underestimated covariance could lead a chemical plant operator to believe that the state of a chemical reaction is comfortably within safe operating bounds when in fact the magnitude of the errors in the state estimate are sufficiently large that the true state could easily be outside of the bounds.
(The terms mean and covariance sometimes will be used hereafter as abbreviations for state vector and error matrix, respectively, in a manner consistent with colloquial usage in the fields of estimation, filtering, and control.)
A measuring device typically generates a signal that is related according to known equations or physical laws to the state of a physical system that is measured by the device. By using the equations or physical laws, the signal produced by the measuring device may be converted into quantities representing the values of variables of interest, such as temperature or pressure, relating to the state of the system. The variables of interest can then be indexed so that they can be represented in the form of a vector wherein each element of the vector corresponds to a specific variable. The value for each variable derived from the signal produced by the measuring device can then be associated with an element of the vector corresponding to that variable. It is common for the indices of the vector to correspond to addresses of machine readable memory in which the values can be stored for manipulation by a general purpose computer.
By repeatedly measuring the state of a system whose true state is already known, it is possible to determine the actual errors in the measurements by examining the difference between each measurement vector and the vector corresponding to the true state of the system. Using standard methods, the set of measurement errors can be processed to produce a model for generating an estimated error covariance matrix for any subsequent measurement vector produced from the device. In many cases it is also possible to estimate the error covariance matrix associated with a measurement vector using known equations and physical laws that relate the measuring device and the system being measured. These and other methods for generating mean and covariance estimates from signals produced from measuring devices are well known and widely used in traditional signal processing systems.
The prior state-of-the-art methods for applying nonlinear transformations to mean and covariance estimates derived from measurements of physical systems are described in U.S. Pat. No. 5,627,768: "Signal Processing System and Method for Performing a Nonlinear Transformation." U.S. Pat. No. 5,627,768 describes a method and apparatus for applying a nonlinear transformation to a given estimate {a,A} by (1) determining a set of vectors having its mean equal to a and its covariance equal to A, (2) applying the desired nonlinear transformation to each element of this set of vectors, and (3) computing the mean and covariance of the resulting transformed set of vectors. The present invention, however, offers various advantages by providing a complementary method for computing the transformed mean according to a scheme other than calculating the mean of the transformed set of vectors. For example, it is often computationally more efficient to compute the transformed mean by simply applying the nonlinear function to a.
The covariance of a set of m column vectors {v.sub.1, v.sub.2, . . . ,v.sub.m } about a column vector a is defined to be the sum 1/m*(v.sub.i -a)*(v.sub.i -a).sup.T for all i between 1 and m. The key observation behind the present invention is that the computed covariance about the vector a is identical to what would have been obtained had the set of vectors included the additional elements {2*a-v.sub.1, 2*a-v.sub.2, . . . , 2*a-v.sub.m }. This means that if the nonlinear function f( ) is assumed to be symmetric with respect to a, i.e. f(a+u)=f(a-u) for any vector u, then as few as half the number of sample vectors are required for the present invention as would be used in the method of U.S. Pat. No. 5,627,768. Although many nonlinear functions do satisfy these symmetry assumptions, e.g., diffusion-type equations, many others are approximately symmetric so that the computational advantages of assumed symmetry provided by the present invention can actually permit a signal processing system to achieve greater accuracy by accommodating higher update rates, i.e., by allowing more sensor measurements--hence more information--to be processed per unit of time. This improved accuracy is achieved even though deviations from true symmetry may mean that individual sensor measurements are processed less accurately than more sophisticated and computationally intensive methods.
Like U.S. Pat. No. 5,627,768, the present invention also provides a method for independently weighting elements of the chosen set of m vectors to be nearer to or further away from the mean a, while ensuring that the covariance of the set about a is A. This is advantageous when it is desirable to diminish or amplify the effects of a nonlinear transformation on vectors that are relatively far away from the mean. It is most intuitive to interpret a real-valued weight w.sub.i corresponding to a vector v.sub.i as implying that there are w.sub.i copies of v.sub.i. Thus the mean of a set of weighted vectors is just the sum of w.sub.i *v.sub.i, for all i from 1 to the number of vectors, divided by the number of vectors, i.e., divided by the sum of the weights. The advantages of associating weights with vectors are that it avoids the need to explicitly maintain multiple copies of vectors and it allows the flexibility to include fractional copies of vectors.
Any randomly or deterministically selected set of m weights {w.sub.1,w.sub.2, . . . ,w.sub.m } whose sum is W, and set of vectors {v.sub.1,v.sub.2, . . . ,v.sub.m } whose mean is nonzero and whose covariance about zero (i.e., the sum of 1/W*w.sub.i *v.sub.i *v.sub.i.sup.T for i ranging from 1 to m) is a nonsingular matrix P, can be transformed to ensure that the weighted covariance about the zero vector is A (i.e., the sum of 1/W*w.sub.i *v.sub.i *v.sub.i.sup.T is equal to A). This can be accomplished simply by multiplying each vector v.sub.i by the inverse of the matrix square root of P, and then multiplying by the matrix square root of A. This is because the multiplication by the inverse matrix square root of P produces a set of vectors whose covariance about the zero vector is equal to the identity matrix; and the subsequent multiplication by the matrix square root of A then produces a set of vectors whose covariance about the zero vector is equal to A. Adding a to each element of this transformed set of vectors then results in a set of vectors whose covariance about a is equal to A. (There are many other conventional linear algebra methods for constructing a set of vectors having a given mean and covariance, and any one of these methods can be applied in place the method just described.)
Unlike U.S. Pat. No. 5,627,768, the present invention also provides a method for estimating the transformed covariance using any desired estimate of the transformed mean. For example, whereas the method of U.S. Pat. No. 5,627,768 calculates the transformed mean a.sup.+ (using different notation than that used in this document) as being the mean of the transformed set of vectors, the present invention permits the transformed mean to be calculated according to any chosen method by defining the transformed covariance to be simply the covariance about a.sup.+ of the transformed set of vectors. This method is advantageous when a reliable method is known for estimating the transformed mean and what is needed is just a method for estimating the transformed covariance about that estimated transformed mean.
The key value of the present invention is that it provides a complement to that of U.S. Pat. No. 5,627,768 (i.e., the sets of possible signal processing systems defined by that invention and this invention are completely disjoint), with the present invention providing more computationally efficient means for estimating means and covariances resulting from nonlinear transformations.